package com.example.demo.leetcode;

import org.w3c.dom.NodeList;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * leetCode题目实例
 */
public class Example {
    public static void main(String[] args){
        int[] candidates = new int[]{4,1,1,4,4,4,4,2,3,5};
        int target = 10;



        Example example = new Example();

        int[] nums = new int[]{-3,-1,0,2,4,5};

        System.out.println(example.fourSum(nums,2));

    }

    /**
     * 两数之和
     */
    public static void coding1(){
        int[] nums = new int[]{3,2,4};
        int target = 6;

        int[] res = new int[2];
        Map<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target - nums[i])){
                res[0] = map.get(target - nums[i]);
                res[1] = i;
            }
            map.put(nums[i],i);
        }

        System.out.println(Arrays.toString(res));
    }

    /**
     * 组合总和 II
     * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。
     * 所有数字（包括目标数）都是正整数。
     * 解集不能包含重复的组合。
     * @param candidates
     * @param target
     * @return [1, 1, 2, 3, 4, 4, 4, 4, 4, 5]
     */
    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum2(int[] candidates,int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum3(int[] candidates,int target) {
        Arrays.sort(candidates);

        for(int num : candidates){

        }

        return null;
    }

    public void dfs(List<Integer> numLists,int[] candidates){
        for(int num : candidates){

        }
    }

    public boolean isPalindrome(int x) {
        if(x < 0 || (x %10 == 0 && x != 0)){
            return false;
        }

        int tmp = 0;
        while (x > tmp){
            tmp = tmp * 10 + x % 10;
            System.out.println(tmp);
            x /= 10;
        }

        return tmp == x || x == tmp/10;
    }

    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length <= 0){
            return "";
        }

        for(int i=0;i<strs.length;i++){
            String str = strs[i];

            String strTmp = str.replaceAll("[a-z]","");

            if(!"".equals(strTmp)){
                return "";
            }
        }

        int index = 0;
        boolean isBlank = false;
        boolean needBreak = false;
        List<Character> result = new ArrayList<>();

        while (true){
            char strTmp = 0;
            for(int i=0;i<strs.length;i++){
                String str = strs[i];
                char[] strCharArr = str.toCharArray();

                //已经遍历完了
                if(index > strCharArr.length - 1){
                    needBreak = true;
                    break;
                }

                if(i == 0){
                    strTmp = strCharArr[index];
                    System.out.println(strTmp);
                }
                else if(strCharArr[index] != strTmp){
                    //如果不相等
                    needBreak = true;
                    if(index == 0){
                        //首字母不相等，说明没有相同的字母
                        isBlank = true;
                    }
                    break;
                }
            }

            if(needBreak){
                break;
            }

            result.add(strTmp);

            index ++;
        }

        //首字母不相等，说明没有相同的字母
        if(isBlank){
            return "";
        }

        System.out.println(result.toString());

        if(result.size() <= 0){
            return "";
        }
       else {
            char[] resCharArr = new char[result.size()];
            for(int i=0;i<result.size();i++){
                resCharArr[i] = result.get(i);
            }

            return new String(resCharArr);
        }
    }

    public boolean isValid(String s) {
        if(s != null && !"".equals(s)){
            LinkedList<Character> stack = new LinkedList<>();

            for (char c : s.toCharArray()) {
                if (c == '['){
                    stack.push(']');
                }
                else if (c == '(') {
                    stack.push(')');
                }
                else if (c == '{') {
                    stack.push('}');
                }
                else if (stack.isEmpty() || c != stack.pop()) {
                    return false;
                }
            }
            return stack.isEmpty();
        }

        return false;
    }

    public int removeDuplicates(int[] nums) {
        if (nums.length == 0){
            return 0;
        }

        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        System.out.println(Arrays.toString(nums));
        return i + 1;
    }

    /**
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        int r = 0;

        for(int i=0;i<nums.length;i++){
            if(i == nums.length - r){
                break;
            }

            if(nums[i] == val){
                if(i == nums.length-1){
                    nums[i] = 0;
                    r ++;
                }
                else {
                    for(int j=i+1;j<nums.length-r;j++){
                        nums[j - 1] = nums[j];
                    }

                    r ++;
                    nums[nums.length - r] = 0;

                    if(nums[i] == val){
                        i --;
                    }
                }
            }
        }

        System.out.println(Arrays.toString(nums));

        return nums.length - r;
    }

    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    public int searchInsert(int[] nums, int target) {
        int res = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i] >= target){
                res = i;
                break;
            }
            else {
                res = i+1;
            }
        }

        return res;
    }

    /**
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int maxNum = nums[0];
        int preIndex = 0;
        for(int i=0;i<nums.length;i++){
            preIndex = Math.max(preIndex+nums[i],nums[i]);
            maxNum = Math.max(preIndex,maxNum);
        }
        /*int index = 0;
        while (index < nums.length){
            for(int i=0;i<nums.length-index;i++){
                System.out.print(nums[i]+",");
                int totalTmp = nums[i];

                for(int j=1;j<=index;j++){
                    System.out.print(nums[i+j]+",");
                    totalTmp += nums[i+j];
                }
                if(maxNum < totalTmp){
                    maxNum = totalTmp;
                }

                System.out.println("");
            }

            System.out.println("-----------组合分割----------");

            index ++;
        }*/

        return maxNum;
    }

    public int lengthOfLastWord(String s) {
        String[] sArr = s.split(" ");
        for(int i=sArr.length-1;i>=0;i--){
            if(!"".equals(sArr[i])){
                return sArr[i].length();
            }
        }

        return 0;
    }

    public int[] plusOne(int[] digits) {
        for(int i=digits.length-1;i>=0;i--){
            digits[i] ++;
            digits[i] = digits[i]%10;
            if(digits[i] != 0){
                return digits;
            }
        }

        digits = new int[digits.length + 1];
        digits[0] = 1;

        return digits;
    }

    public String addBinary(String a, String b) {

        return null;
    }

    /**
     * 3. 无重复字符的最长子串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }

        Map<Character,Integer> map = new HashMap<>();
        int ans = 0;
        int len = s.length();

        int left =0;

        for(int i=0;i<len;i++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }

            map.put(s.charAt(i),i);
            ans = Math.max(ans,i-left+1);
        }


        return ans;
    }

    public int myAtoi(String s) {
        if(s == null){
            return 0;
        }

        long l = -+999999999;

        s = s.trim();
        int len = s.length();
        if(len == 0){
            return 0;
        }


        char fist = s.charAt(0);
        boolean isFistNum = false;
        String numStr = fist + "";

        try{
            Integer.parseInt(fist+"");
        }catch (Exception e){
            if(!"-".equals(fist + "") && !"+".equals(fist + "")){
                return 0;
            }
            if("+".equals(fist + "")){
                numStr = "";
            }
            else {
                isFistNum = true;
            }
        }

        for(int i=1;i<len;i++){
            char c = s.charAt(i);

            try{
                int num = Integer.parseInt(c+"");
                numStr += num;
                System.out.println(num);
            }catch (Exception e){
                break;
            }
        }

        int res = 0;
        try{
            res = Integer.parseInt(numStr);
        }catch (Exception e){
            if(isFistNum){
                res = Integer.MIN_VALUE;
            }
            else {
                res = Integer.MAX_VALUE;
            }
        }

        return res;
    }

    /**
     * 11. 盛最多水的容器
     * @param height
     * @return  4913370
     */
    public int maxArea(int[] height) {
        /*List<Integer> dataLists = new ArrayList<>();

        for(int i=0;i<height.length;i++){
            int y1 = height[i];
            for(int j=i+1;j<height.length;j++){
                int y2 = height[j];

                int x = (j+1) - (i + 1);
                int w = Math.min(y1,y2) * x;
                dataLists.add(w);
            }
        }

        System.out.println(dataLists.toString());

        int max = 0;
        for(int i=0;i<dataLists.size();i++){
            max = Math.max(max,dataLists.get(i));
        }

        return max;*/
        int left = 0;
        int right = height.length - 1;
        int max = 0;

        while (left != right){
            int y1 = height[left];
            int y2 = height[right];
            int min = Math.min(y1,y2);

            System.out.println(y1+","+y2);

            int w = min * (right - left);
            max = Math.max(max,w);

            if(min == y1){
                left ++;
            }
            else {
                right --;
            }
        }

        return max;
    }

    /**
     * 15. 三数之和
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        if(nums != null && nums.length >= 3){
            int len = nums.length;
            Arrays.sort(nums);

            for(int fist=0;fist<len;++fist){
                //需要和上一次不一样
                if(fist > 0 && nums[fist] == nums[fist - 1]){
                    continue;
                }

                //指针指向数组最右端
                int third = len - 1;
                int target = -nums[fist];

                for(int second=fist+1;second<len;++second){
                    //需要和上一次不一样
                    if(second > fist+1 && nums[second] == nums[second-1]){
                        continue;
                    }

                    //需要保证b的指针在c指针的右端
                    while (second < third && nums[second] + nums[third] > target){
                        --third;
                    }

                    //如果指针重合，随着b后续增加，就不会有满足a+b+c=0并且b<c了
                    if(second == third){
                        break;
                    }

                    if(nums[second] + nums[third] == target){
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[fist]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        result.add(list);
                    }
                }
            }
        }

        System.out.println(result.toString());

        return result;
    }

    /**
     * 16. 最接近的三数之和
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        if(nums != null && nums.length >= 3){
            Arrays.sort(nums);

            int result = nums[0] + nums[1] + nums[2];
            int len = nums.length;

            for(int i=0;i<len;i++){
                if(i > 0 && nums[i] == nums[i - 1]){
                    continue;
                }

                int left = i + 1;
                int right = len - 1;

                while (left < right){
                    int sum = nums[i] + nums[left] + nums[right];
                    if(sum == target){
                        return sum;
                    }

                    if(Math.abs(sum - target) < Math.abs(result - target)){
                        result = sum;
                    }

                    if(sum > target){
                        int right0 = right - 1;
                        while (left < right0 && nums[right0] == nums[right]){
                            right0 --;
                        }
                        right = right0;
                    }
                    else {
                        int left0 = left + 1;
                        while (left0 < right && nums[left] == nums[left0]){
                            left0 ++;
                        }

                        left = left0;
                    }
                }
            }

            return result;

        }

        return 0;
    }

    /**
     * 17. 电话号码的字母组合
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        List<String> resultLists = new ArrayList<>();

        if(digits.length() > 0){
            Map<Character,String[]> charMaps = new HashMap<>();
            charMaps.put('2',new String[]{"a","b","c"});
            charMaps.put('3',new String[]{"d","e","f"});
            charMaps.put('4',new String[]{"g","h","i"});
            charMaps.put('5',new String[]{"j","k","l"});
            charMaps.put('6',new String[]{"m","n","o"});
            charMaps.put('7',new String[]{"p","q","r","s"});
            charMaps.put('8',new String[]{"t","u","v"});
            charMaps.put('9',new String[]{"w","x","y","z"});

            int index = 0;
            StringBuilder combination = new StringBuilder();

            backtrack(index,digits,charMaps,resultLists,combination);
        }


        return resultLists;
    }

    public void backtrack(int index,String digits,Map<Character,String[]> charMaps,List<String> resultLists,StringBuilder combination){
        if(index == digits.length()){
            resultLists.add(combination.toString());
        }
        else {
            String[] phoneArr = charMaps.get(digits.charAt(index));
            for(int i=0;i<phoneArr.length;i++){
                combination.append(phoneArr[i]);

                backtrack(index + 1,digits,charMaps,resultLists,combination);

                combination.deleteCharAt(index);
            }
        }

    }

    /**
     * 18、四数之和
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();

        if(nums != null && nums.length > 3){
            Arrays.sort(nums);

            int len = nums.length;

            for(int fist=0;fist<len;fist++){
                for(int second=fist+1;second<len;second++){
                    int third = second + 1;
                    int four = len - 1;

                    //先移动左指针
                    while (third < four){
                        int sum = nums[fist] + nums[second] + nums[third] + nums[four];
                        if(sum == target){
                            List<Integer> temp = new ArrayList<>();
                            temp.add(nums[fist]);
                            temp.add(nums[second]);
                            temp.add(nums[third]);
                            temp.add(nums[four]);
                            if(!result.contains(temp)){
                                result.add(temp);
                            }
                            while (third < four && nums[third] == nums[third + 1]){
                                third ++;
                            }
                            third ++;

                            while (third < four && nums[four] == nums[four - 1]){
                                four --;
                            }
                            four --;
                        }
                        else if(sum < target){
                            third ++;
                        }
                        else {
                            four --;
                        }
                    }
                }
            }
        }

        return result;
    }
}
